package cn.cxq.learning.array;

import java.util.HashSet;
import java.util.Set;

/**
 * 剑指offer
 * 数组中重复的数字
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M 热度指数：22651
 * 本题知识点： 数组
 * 算法知识视频讲解
 * 题目描述
 * 在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任一一个重复的数字。 例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1
 * 示例1
 * 输入
 * 复制
 * [2,3,1,0,2,5,3]
 * 返回值
 * 复制
 * 2或3
 */
public class RepeatedNumber {

//    间 52ms
//    占用内存 13652KB
    //使用等长数组,充分利用题干
    public int duplicate(int[] numbers) {
        int[] numOfNumbers = new int[numbers.length];

        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] >= numbers.length || numbers[i] < 0) {
                return -1;
            }
            numOfNumbers[numbers[i]]++;
            if (numOfNumbers[numbers[i]] >1) return numbers[i];
        }

        return -1;
    }

//    运行时间：66ms
//    超过32.49%用Java提交的代码
//    占用内存：14700KB
//    超过21.33%用Java提交的代码
    //重复性问题可以想到set
//    public int duplicate(int[] numbers) {
//
//        for (int i = 0; i < numbers.length; i++) {
//            if (numbers[i] >= numbers.length || numbers[i] < 0) {
//                return -1;
//            }
//        }
//
//        Set<Integer> set = new HashSet<>();
//
//        for (int i = 0; i < numbers.length; i++) {
//            set.add(numbers[i]);
//            if (set.size() != i + 1) {
//                return numbers[i];
//            }
//        }
//        return -1;
//    }

//    运行时间 75ms
//    占用内存 13732KB
//    public int duplicate(int[] numbers) {
//        // write code here
//
//        for (int i = 0; i < numbers.length; i++) {
//            if (numbers[i] >= numbers.length || numbers[i] < 0) {
//                return -1;
//            }
//        }
//
//        for (int i = 0; i < numbers.length; i++) {
//            for (int j = i + 1; j < numbers.length; j++) {
//                if (numbers[i] == numbers[j]) {
//                    return numbers[i];
//                }
//            }
//        }
//        return -1;
//    }

}
